import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;


public class MergeSort {

	public static Comparable[] mergeSort(Comparable[] a){
		int p = a.length/2;
		Comparable[] l = new Comparable[p];
		Comparable[] r = new Comparable[(a.length%2 == 0)? p : p+1 ];
		if (a.length <= 1){
			return a;
		}
		for(int i = 0; i<a.length; i++){
			if (i<p)
				l[i]=a[i];
			else
				r[i-p]=a[i];
		}
		l = mergeSort(l);
		r = mergeSort(r);
		return merge(l,r);
	}
	
	private static Comparable[] merge(Comparable[] l, Comparable[] r){
		Comparable[] n = new Comparable[l.length+r.length];
		int i=0;
		int j=0;
		int m=0;
		while (i<l.length && j < r.length){
			if (l[i].compareTo(r[j]) < 0){
				n[m]=l[i];
				m++;
				i++;
			}
			else {
				n[m]=r[j];
				j++;
				m++;
			}
		}
		while(i<l.length){
			n[m] = l[i];
			m++;
			i++;
		}
		while(j<r.length){
			n[m] = r[j];
			m++;
			j++;
		}
				
		return n;
	}
}